package com.code.nowcoder;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/29 17:01
 */
public class W_The67 {

    PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
    int limit;

    public int solve (int n, int m, int P, int[] a, int[] d, int k) {
        // write code here
        limit = m;

        for (int i = 0; i < n; i += 1) {
            if (a[i] == k) addElement(0);
            else {
                long inv = gcdExt(d[i], P)[1];
                addElement((int) (((k - a[i]) * inv % P + P) % P));
            }
        }
        return queue.peek();
    }

    long[] gcdExt(int a, int b) {
        if (b == 0) return new long[]{a, 1, 0};
        long[] res = gcdExt(b, a % b);
        return new long[]{res[0], res[2], res[1] - (a / b) * res[2]};
    }

    void addElement(int n) {
        queue.add(n);

        if (queue.size() > limit) queue.poll();
    }

    public static void main(String[] args) {
        W_The67 the67 = new W_The67();
        int solve = the67.solve(2, 1, 131, new int[]{103, 101}, new int[]{3, 56}, 37);
        System.out.println(solve);
    }
}
